W10. Хеш-таблицы, chaining, open addressing и хеш-функции

Автор

Nikolai Kudasov

Дата публикации

24 марта 2026 г.

1. Краткое содержание

1.1 Словари и множества
1.1.1 Абстрактный тип данных «словарь»

Словарь (dictionary), также map, — один из базовых абстрактных типов данных (ADT): коллекция пар ключ–значение (key–value pairs); каждому ключу соответствует ровно одно значение. Аналогия — бумажный словарь: по ключу (слову) находим значение (определение).

Три основные операции:

  • put(k, v) — вставить пару; если ключ \(k\) уже есть, старое значение заменяется на \(v\).
  • get(k) — получить значение по ключу \(k\); если ключа нет, возвращается NIL.
  • remove(k) — удалить запись с ключом \(k\).

Важно: для каждого ключа хранится не больше одного значения — отличие от multimap.

1.1.2 Словарь на двусвязном списке

Простейшая реализация — узлы doubly linked list с парами ключ–значение.

В худшем случае все операции требуют просмотра списка:

  • get(k): \(\mathcal{O}(n)\)
  • put(k, v): \(\mathcal{O}(n)\) — проверка дубликатов
  • remove(k): \(\mathcal{O}(n)\) поиска; \(\mathcal{O}(1)\) при указателе на узел

Для больших словарей это медленно.

1.1.3 Словарь на массиве (direct-address table)

Если ключи — целые от \(0\) до \(n-1\), можно хранить значения в массиве: array[k] = v. Это прямая адресация (direct-address table).

Все три операции — \(\mathcal{O}(1)\) в худшем случае.

Ограничение: если universe of keys \(U\) огромен (строки, 64-битные целые), массив на все возможные ключи нереалистичен. Выход — хеш-функция (hash function), сжимающая \(U\) до диапазона размера таблицы.

1.2 Хеш-таблицы: основные идеи
1.2.1 Что такое hash table?

Хеш-таблица (hash table) сочетает скорость массива с гибкостью произвольных ключей:

  1. Массив \(T\) размера \(m \ll |U|\).
  2. Hash function \(h : U \to \{0, 1, \dots, m-1\}\).
  3. Пара ключ–значение хранится в ячейке \(h(k)\).

При удачных условиях операции в среднем \(\mathcal{O}(1)\). Проблема — коллизия (collision): разные ключи попадают в один индекс; нужна стратегия разрешения.

1.2.2 Хеш-функции

Hash function:

\[h : U \to \{0, 1, \dots, m - 1\}\]

Значение \(h(k)\) — hash ключа \(k\).

Примеры:

\[h_1 : \mathbb{N} \to \{0, 1, \dots, 15\}, \quad h_1(n) = (n + 7) \bmod 16\]

\[h_2 : \text{String} \to \{0, 1, \dots, 255\}, \quad h_2(s) = \left(\sum_{i=0}^{|s|-1} \text{ord}(s[i])\right) \bmod 256\]

где \(\text{ord}(c)\) — код символа \(c\) (например ASCII).

1.2.3 Коллизии

Collision: \(h(k_1)=h(k_2)\) при \(k_1 \neq k_2\). При \(|U|>m\) коллизии неизбежны (pigeonhole principle). Две главные стратегии:

  1. Chaining — список всех пар в слоте.
  2. Open addressing — поиск свободной ячейки внутри массива (probing).
1.3 Chaining
1.3.1 Как работает chaining

В chaining каждый слот — linked list (часто двусвязный) записей с данным \(h(k)\). Вставка:

  1. Вычислить \(h(k)\).
  2. Добавить запись в голову списка в слоте \(h(k)\).
1.3.2 Сложность chaining

Худший случай: все \(n\) ключей в один слот, длина цепочки \(n\).

  • put: \(\mathcal{O}(1)\) при prepend и различных ключах; \(\mathcal{O}(n)\) в абсолютном худшем случае.
  • get: \(\mathcal{O}(n)\).
  • remove(entry): \(\mathcal{O}(1)\) при указателе на запись в двусвязном списке.

Средний случай: параметр load factor \(\alpha = n/m\). При simple uniform hashing ожидаемая длина цепочки в слоте — \(\alpha\).

Средние оценки:

  • put: \(\mathcal{O}(1 + \alpha)\)
  • get: \(\mathcal{O}(1 + \alpha)\)
  • remove(entry): \(\mathcal{O}(1)\)

Если \(\alpha\) ограничен константой (перехеширование при росте), операции «по сути» \(\mathcal{O}(1)\).

Для chaining \(\alpha\) может быть любым \(\geq 0\) — нет требования \(\alpha \leq 1\).

1.4 Open addressing
1.4.1 Идея

В open addressing в ячейке не больше одной записи; при коллизии выполняется probe по probe sequence:

\[h(k, 0), \; h(k, 1), \; \dots, \; h(k, m-1)\]

Обычно это перестановка индексов \(\{0,\dots,m-1\}\). Вставка — в первую пустую ячейку последовательности.

Тогда \(\alpha = n/m \leq 1\).

1.4.2 Linear probing

\[h(k, i) = (h_1(k) + i) \bmod m\]

Плюс: простота и локальность памяти. Минус: primary clustering — длинные занятые отрезки.

1.4.3 Double hashing

\[h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m\]

Чтобы обойти все \(m\) ячеек, \(h_2(k)\) должно быть взаимно просто с \(m\) для каждого ключа. Частый выбор при простом \(p\): \(h_2(k)=1+(k \bmod (p-1))\).

1.4.4 Вставка, поиск, удаление

Вставка идёт по probe sequence до первой пустой ячейки:

HASH-INSERT(T, k)
1  i = 0
2  repeat
3      q = h(k, i)
4      if T[q] == NIL
5          T[q] = k
6          return q
7      else i = i + 1
8  until i == m
9  error "hash table overflow"

Поиск использует ту же последовательность и останавливается при нахождении ключа или пустом слоте NIL:

HASH-SEARCH(T, k)
1  i = 0
2  repeat
3      q = h(k, i)
4      if T[q] == k
5          return q
6      i = i + 1
7  until T[q] == NIL or i == m
8  return NIL

Почему останов на NIL корректна: при вставке \(k\) он попал в первую пустую ячейку своей последовательности; если поиск дошёл до пустого раньше, чем до \(k\), ключа не было.

Удаление: маркер DELETED — при поиске считается занятым (продолжаем пробовать), при вставке — свободным. Минус — накопление «дырок» и деградация производительности.

1.4.5 Сложность open addressing

При uniform hashing (равновероятная перестановка слотов для каждого ключа):

  • put / get: в среднем \(\mathcal{O}\!\left(\frac{1}{1-\alpha}\right)\)
  • remove: зависит от стратегии

При \(\alpha\) с запасом меньше 1 — по сути \(\mathcal{O}(1)\); при \(\alpha \to 1\) производительность падает.

1.4.6 Сравнение: список vs chaining vs open addressing
Operation Doubly linked list Chaining Open addressing
put(k, v) \(\mathcal{O}(1)\) or \(\mathcal{O}(n)\) \(\mathcal{O}(1 + \alpha)\) avg. \(\mathcal{O}\!\left(\frac{1}{1-\alpha}\right)\) avg.
get(k) \(\mathcal{O}(n)\) \(\mathcal{O}(1 + \alpha)\) avg. \(\mathcal{O}\!\left(\frac{1}{1-\alpha}\right)\) avg.
remove(entry) \(\mathcal{O}(1)\) \(\mathcal{O}(1)\) depends on strategy
Load factor \(\alpha\) — \(0 \le \alpha < \infty\) \(0 \le \alpha \le 1\)
1.5 Хеш-функции подробнее
1.5.1 Двухэтапное хеширование

\[h(k) = \text{compress}(\text{hashCode}(k))\]

  1. hashCode \(: U \to \mathbb{Z}\) — целое (может быть большим).
  2. compress \(: \mathbb{Z} \to \{0,\dots,m-1\}\) — индекс таблицы.
1.5.2 Стратегии hashCode

Типовые идеи hashCode: адрес объекта в памяти, приведение битов к int, сумма компонент ключа, polynomial rolling hash. У простой суммы перестановка символов часто даёт ту же сумму и лишнюю collision; полиномиальная схема (в духе схемы Горнера) обычно чувствительнее к порядку символов и даёт лучшее распределение.

1.5.3 Функции сжатия

Division method: \(h(k)=k \bmod m\) — избегать \(m=2^p\) или \(10^p\) из-за кластеризации младших разрядов.

Multiplication method: \(h(k)=\lfloor m(kA \bmod 1)\rfloor\), \(A \in (0,1)\) (часто \(\approx (\sqrt5-1)/2\)).

1.5.4 Свойства «хорошей» хеш-функции
  1. Uniformity — равномерное попадание в слоты.
  2. Determinism — равные ключи → равный hash.
  3. Speed — \(\mathcal{O}(1)\) или близко.

Для hash table не нужна криптостойкость (SHA-256 избыточен).

1.6 Математический анализ сложности
1.6.1 Chaining: предпосылки

Таблица \(m\) слотов, \(n\) записей, \(\alpha=n/m\), simple uniform hashing, время вычисления \(h\) — \(\mathcal{O}(1)\). Ожидаемая длина цепочки \(E[n_i]=\alpha\).

1.6.2 Chaining: неуспешный поиск

Теорема (Cormen et al. 2022, Theorem 11.1). При разрешении коллизий методом chaining неуспешный поиск в среднем занимает время \(\Theta(1 + \alpha)\) при simple uniform hashing.

Доказательство. Неуспешный поиск для ключа \(k\) вычисляет \(h(k)\) за \(\mathcal{O}(1)\) и проходит всю цепочку в слоте \(h(k)\) длины \(n_{h(k)}\): \(T(n,k)=1+n_{h(k)}\), откуда \(E[T]=1+E[n_{h(k)}]=1+\alpha\). \(\square\)

1.6.3 Chaining: успешный поиск

Теорема (Cormen et al. 2022, Theorem 11.2). При chaining успешный поиск в среднем занимает \(\Theta(1 + \alpha)\) при simple uniform hashing.

Идея доказательства. Если ключи вставлялись в порядке \(k_1,\dots,k_n\) и ищется равновероятно один из них, ожидаемое число дополнительных проверок в цепочке сводится к \(\frac{\alpha}{2}-\frac{1}{2n}\), вместе с вычислением \(h\) получаем \(\Theta(1+\alpha)\). \(\square\)

1.6.4 Open addressing: предпосылки

Таблица \(m\), \(n\) записей, \(\alpha=n/m\leq 1\), uniform hashing, время \(h\) — \(\mathcal{O}(1)\).

1.6.5 Open addressing: неуспешный поиск

Теорема (Cormen et al. 2022, Theorem 11.6). Ожидаемое число проб при неуспешном поиске не превосходит \(\dfrac{1}{1-\alpha}\).

Идея. Вероятность сделать не меньше \(i\) проб ограничивается \(\alpha^{i-1}\); суммирование даёт геометрический ряд \(\frac{1}{1-\alpha}\).

1.6.6 Open addressing: успешный поиск

Теорема (Cormen et al. 2022, Theorem 11.8). Ожидаемое число проб при успешном поиске не превосходит \(\dfrac{1}{\alpha}\ln\dfrac{1}{1-\alpha}\).

Идея. Поиск ключа, вставленного \((i+1)\)-м, повторяет путь вставки при загрузке \(i/m\); усреднение даёт гармоническую сумму, которую оценивают интегралом \(\ln\frac{m}{m-n}=\ln\frac{1}{1-\alpha}\).

2. Определения

  • Dictionary (Map): ADT пар ключ–значение с put, get, remove; не более одного значения на ключ.
  • Hash table: реализация словаря массивом \(T\) размера \(m\) и функцией \(h\).
  • Hash function: \(h : U \to \{0,\dots,m-1\}\); значение \(h(k)\) — hash ключа \(k\).
  • Collision: \(h(k_1)=h(k_2)\), \(k_1 \neq k_2\).
  • Load factor (\(\alpha\)): \(\alpha=n/m\).
  • Chaining: в слоте — список записей с данным hash.
  • Open addressing: одна запись на слот; коллизии — через probe sequence.
  • Probe sequence: \(h(k,0),\dots,h(k,m-1)\).
  • Linear probing: \(h(k,i)=(h_1(k)+i)\bmod m\).
  • Double hashing: \(h(k,i)=(h_1(k)+i\cdot h_2(k))\bmod m\).
  • Primary clustering: скопления занятых ячеек при linear probing.
  • DELETED marker: служебное значение для удаления в open addressing.
  • Hash code: этап \(\text{hashCode}:U\to\mathbb{Z}\).
  • Compression function: этап \(\text{compress}:\mathbb{Z}\to\{0,\dots,m-1\}\).
  • Simple uniform hashing: равновероятный независимый выбор слота для каждого ключа.
  • Uniform hashing: равновероятная перестановка проб для каждого ключа (анализ open addressing).
  • Direct-address table: \(h(k)=k\) на \(\{0,\dots,m-1\}\); \(\mathcal{O}(1)\) при возможности выделить массив.

3. Формулы

  • Load factor: \(\alpha = \dfrac{n}{m}\)
  • Ожидаемая длина цепочки (chaining): \(E[n_i] = \alpha\) при simple uniform hashing
  • Chaining — неуспешный поиск: \(\Theta(1 + \alpha)\)
  • Chaining — успешный поиск: \(\Theta(1 + \alpha)\)
  • Linear probing: \(h(k, i) = (h_1(k) + i) \bmod m\)
  • Double hashing: \(h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m\)
  • Open addressing — неуспешный поиск: \(\le \dfrac{1}{1 - \alpha}\) проб в среднем
  • Open addressing — успешный поиск: \(\le \dfrac{1}{\alpha} \ln \dfrac{1}{1-\alpha}\)
  • Division method: \(h(k) = k \bmod m\)
  • Multiplication method: \(h(k) = \lfloor m (kA \bmod 1) \rfloor\), \(A \in (0,1)\)
  • Polynomial hash code: \(\text{hashCode}(k) = k_0 + k_1 a + \dots + k_{n-1} a^{n-1}\)
  • Ряд: \(\sum_{i=0}^\infty \alpha^i = \dfrac{1}{1-\alpha}\) при \(|\alpha|<1\)

4. Примеры и задания

4.1. Linear probing с квадратичной хеш-функцией (Набор задач 8, Задание 1)

Рассмотрите хеш-таблицу из 11 слотов (индексы \(0,\dots,10\)) и первичную хеш-функцию \(h(k)=(k^2+5k+4)\bmod 11\). Вставьте ключи в указанном порядке, используя linear probing:

\[4, \; 19, \; 27, \; 8, \; 15, \; 11, \; 23, \; 6, \; 31, \; 14, \; 2\]

(a) Итоговое состояние таблицы. (b) Для ключа 31 — последовательность индексов проб до размещения. (c) После всех вставок: максимальное число проб при неуспешном поиске?

Нажмите, чтобы увидеть решение

Ключевая идея: сначала вычисляем \(h(k)\) для каждого ключа, затем применяем linear probing \(h(k,i)=(h(k)+i)\bmod 11\).

  1. Значения \(h(k) = (k^2 + 5k + 4) \bmod 11\):

    \(k\) \(k^2 + 5k + 4\) \(\bmod 11\)
    4 \(16 + 20 + 4 = 40\) 7
    19 \(361 + 95 + 4 = 460\) \(460 \bmod 11 = 9\)
    27 \(729 + 135 + 4 = 868\) \(868 \bmod 11 = 10\)
    8 \(64 + 40 + 4 = 108\) \(108 \bmod 11 = 9\)
    15 \(225 + 75 + 4 = 304\) \(304 \bmod 11 = 7\)
    11 \(121 + 55 + 4 = 180\) \(180 \bmod 11 = 4\)
    23 \(529 + 115 + 4 = 648\) \(648 \bmod 11 = 9\)
    6 \(36 + 30 + 4 = 70\) \(70 \bmod 11 = 4\)
    31 \(961 + 155 + 4 = 1120\) \(1120 \bmod 11 = 9\)
    14 \(196 + 70 + 4 = 270\) \(270 \bmod 11 = 6\)
    2 \(4 + 10 + 4 = 18\) \(18 \bmod 11 = 7\)

  2. Вставка с linear probing:

    • \(k=4\): \(h=7\), слот 7 пуст → 7.
    • \(k=19\): \(h=9\) → 9.
    • \(k=27\): \(h=10\) → 10.
    • \(k=8\): \(h=9\) занят → 10 занят → 0.
    • \(k=15\): \(h=7\) занят → 8.
    • \(k=11\): \(h=4\) → 4.
    • \(k=23\): \(h=9\) занят → 10 занят → 0 занят → 1.
    • \(k=6\): \(h=4\) занят → 5.
    • \(k=31\): \(h=9\) занят → 10 → 0 → 1 заняты → 2.
    • \(k=14\): \(h=6\) → 6.
    • \(k=2\): \(h=7\) занят → … → 3.

  3. Итог:

    Index 0 1 2 3 4 5 6 7 8 9 10
    Key 8 23 31 2 11 6 14 4 15 19 27

(b) Для \(k=31\): \(h(31)=9 \to 10 \to 0 \to 1 \to 2\).

(c) Таблица полна — неуспешный поиск в худшем случае делает 11 проб.

Ответ: (a) таблица выше; (b) \(9,10,0,1,2\); (c) 11.

4.2. Словарь словарей: анализ сложности (Набор задач 8, Задание 2)

Внешний словарь \(A\) по целым ключам, внутренний \(B\) по строкам; параметры \(\alpha,n\) и \(\beta,m\). Заполнить таблицы ожидаемого времени; при \(\alpha=\beta=1/2\) выбрать лучшую пару \((A,B)\).

Нажмите, чтобы увидеть решение

Ключевая идея: поиск пары \((k,s)\) — это поиск \(k\) во внешнем словаре \(A\) и поиск \(s\) во внутреннем \(B\); стоимости складываются.

Ожидаемые времена поиска для реализаций:

Method Unsuccessful Successful
Chaining \(\Theta(1 + \alpha)\) \(\Theta(1 + \alpha)\)
Open addressing \(\Theta\!\left(\frac{1}{1-\alpha}\right)\) \(\Theta\!\left(\frac{1}{\alpha}\ln\frac{1}{1-\alpha}\right)\)
AVL tree \(\Theta(\log n)\) \(\Theta(\log n)\)

(a) Неуспешный поиск (пара \((k,s)\) отсутствует):

\(A \backslash B\) Chaining Open addr. AVL tree
Chaining \(\Theta(1+\alpha) + \Theta(1+\beta)\) \(\Theta(1+\alpha) + \Theta\!\left(\frac{1}{1-\beta}\right)\) \(\Theta(1+\alpha) + \Theta(\log m)\)
Open addr. \(\Theta\!\left(\frac{1}{1-\alpha}\right) + \Theta(1+\beta)\) \(\Theta\!\left(\frac{1}{1-\alpha}\right) + \Theta\!\left(\frac{1}{1-\beta}\right)\) \(\Theta\!\left(\frac{1}{1-\alpha}\right) + \Theta(\log m)\)
AVL tree \(\Theta(\log n) + \Theta(1+\beta)\) \(\Theta(\log n) + \Theta\!\left(\frac{1}{1-\beta}\right)\) \(\Theta(\log n) + \Theta(\log m)\)

Успешный поиск:

\(A \backslash B\) Chaining Open addr. AVL tree
Chaining \(\Theta(1+\alpha) + \Theta(1+\beta)\) \(\Theta(1+\alpha) + \Theta\!\left(\frac{1}{\beta}\ln\frac{1}{1-\beta}\right)\) \(\Theta(1+\alpha) + \Theta(\log m)\)
Open addr. \(\Theta\!\left(\frac{1}{\alpha}\ln\frac{1}{1-\alpha}\right) + \Theta(1+\beta)\) \(\Theta\!\left(\frac{1}{\alpha}\ln\frac{1}{1-\alpha}\right) + \Theta\!\left(\frac{1}{\beta}\ln\frac{1}{1-\beta}\right)\) \(\Theta\!\left(\frac{1}{\alpha}\ln\frac{1}{1-\alpha}\right) + \Theta(\log m)\)
AVL tree \(\Theta(\log n) + \Theta(1+\beta)\) \(\Theta(\log n) + \Theta\!\left(\frac{1}{\beta}\ln\frac{1}{1-\beta}\right)\) \(\Theta(\log n) + \Theta(\log m)\)

(b) При \(\alpha=\beta=\tfrac12\): chaining для обоих уровней даёт \(\Theta(1)\) с наименьшей константой; open addressing тоже \(\Theta(1)\), но с большей константой; AVL даёт \(\Theta(\log n)\) или \(\Theta(\log m)\).

Ответ: минимум при chaining+chaining (или open+open на уровне \(\Theta(1)\)).

4.3. Анализ хеш-функции (Набор задач 8, Задание 3)

Пусть \(h(k)=2k\bmod 7\) и \[S = \{2, 3, 5, 7, 10, 12, 17, 19, 23, 31\}.\] (a) Какие ключи попадают в каждый слот \(j\in\{0,\dots,6\}\)? Какие слоты никогда не используются?

(b) Две различные коллизии.

(c) При chaining и \(m=7\): наибольшая возможная длина цепочки после вставки всех 10 ключей.

(d) Существует ли \(m'\le 10\), что \(h'(k)=k\bmod m'\) инъективна на \(S\)?

Нажмите, чтобы увидеть решение

(a) Таблица \(2k\bmod 7\) даёт используемые слоты \(\{0,3,4,6\}\); никогда не используются \(\{1,2,5\}\).

(b) Например \(h(5)=h(12)=3\); \(h(3)=h(10)=6\).

(c) Максимальная цепочка — 4 (слот 6: \(3,10,17,31\)).

(d) Нужно \(m'\ge 10\) для инъективности 10 ключей; при \(m'=10\) уже есть коллизии (\(2\) и \(12\)), значит такого \(m'\le 10\) нет.

4.4. Хеш-таблица с chaining (Лекция 8, Задание 1)

Вставьте ключи \(5, 28, 19, 15, 20, 33, 12, 17, 10\) в таблицу размера 9 с \(h(k)=k\bmod 9\).

Нажмите, чтобы увидеть решение

Хеши: \(5\to5\), \(28,19,10\to1\), \(15,33\to6\), \(20\to2\), \(12\to3\), \(17\to8\). При добавлении в голову: слот 1 — \(10\to19\to28\); слот 6 — \(33\to15\); остальные одиночные.

Ответ: ненулевые цепочки в слотах 1,2,3,5,6,8; самая длинная — слот 1.

4.5. Double hashing (Лекция 8, Задание 2)

Те же ключи, \(m=11\), \(h_1(k)=(k+1)\bmod 11\), \(h_2(k)=1+(k\bmod 5)\).

Нажмите, чтобы увидеть решение

При данных \(h_1\), \(h_2\) и порядке вставок ключей получаем следующую таблицу:

Index 0 1 2 3 4 5 6 7 8 9 10
Key — 34 8 — 3 12 5 50 — 6 17

Ответ: не более трёх проб на вставку.

4.6. Linear probing (Лекция 8, Задание 3)

Те же ключи, \(h_1(k)=(k+1)\bmod 11\).

Нажмите, чтобы увидеть решение
Index 0 1 2 3 4 5 6 7 8 9 10
Key — — 12 34 3 — 5 50 6 17 8

Ответ: кластер вокруг индекса 7 удлиняет пробирование.

4.7. Отсортированные цепочки (Лекция 8, Задание 4)

Как изменятся худший и средний случаи поиска ключа в chaining, если каждая цепочка — sorted array и внутри делается binary search?

Нажмите, чтобы увидеть решение

Худший случай: поиск улучшается с \(\mathcal{O}(n)\) до \(\mathcal{O}(\log n)\).

Средний случай (при simple uniform hashing): с \(\mathcal{O}(1+\alpha)\) до \(\mathcal{O}(1+\log\alpha)\); при ограниченном \(\alpha\) оба \(\mathcal{O}(1)\).

Вставка: поддержание порядка даёт в среднем \(\mathcal{O}(\alpha)\) для put из-за сдвигов.

Ответ: поиск быстрее в худшем/среднем по логарифму длины цепочки; вставка дороже.

4.8. Верхние границы числа проб (Лекция 8, Задание 5)

Оцените сверху ожидаемое число проб при неуспешном и успешном поиске в open addressing для:

(a) \(\alpha = \dfrac{3}{4}\) (b) \(\alpha = \dfrac{7}{8}\)

Нажмите, чтобы увидеть решение

По теоремам: неуспешный \(\le \frac{1}{1-\alpha}\), успешный \(\le \frac{1}{\alpha}\ln\frac{1}{1-\alpha}\).

\(\alpha\) Неуспешный (верхняя граница) Успешный (верхняя граница)
\(3/4\) 4 \(\approx 1.85\)
\(7/8\) 8 \(\approx 2.38\)

Ответ: при росте заполненности граница для неуспешного поиска растёт примерно обратно пропорционально доле свободных ячеек; успешный — медленнее из-за логарифма.